/*
 * stable_matching.cpp
 *
 *  Created on: Apr 29, 2011
 *      Author: tqlong
 */

#include "matching.h"

void MaximumMatching::NeighborHood1::process(KDTree* node, int j_idx) {
  int j = node->originalIdx(j_idx) + m_matcher.n();
  if (m_matcher.m_matchIdx[m_i] != j && m_matcher.m_prev[j] < 0) { // j is not matched to i and j is not visited
    m_matcher.m_prev[j] = m_i;
    m_matcher.m_queue.push(j);
    if (m_matcher.m_matchIdx[j] < 0)
      m_matcher.m_Y = j;
  }
}

MaximumMatching::MaximumMatching(const dataset_type & set1,
    const dataset_type &set2, double r) :
  Matching(set1, set2), m_r(r), m_tree(new KDTree(m_set2)) {
  m_tree->buildTreeAndStats();
}

MaximumMatching::~MaximumMatching() {
  delete m_tree;
}

void MaximumMatching::doMatch()
{
  m_prev = std::vector<int>(2 * n(), -1);
  m_matchIdx = std::vector<int>(2 * n(), -1);

  m_count = 0;
  for (int i = 0; i < n(); i++) {
    NeighborHood nb(*this, m_set1[i], m_r, false);
    double pruned = m_tree->applyJob(nb);
    if (nb.isFound()) {
      int j = m_tree->originalIdx(nb.m_nearIdx[0]) + n();
      m_matchIdx[i] = j;
      m_matchIdx[j] = i;
      m_count++;
      Log::m_log << "i=" << i << " j=" << j << " pruned=" << pruned
          << " count=" << m_count << endl;
    }
  }

  std::set<int> freeX;
  for (int i = 0; i < n(); i++)
    freeX.insert(i);

  do {
    m_queue = std::queue<int>();
    m_prev = std::vector<int>(2 * n(), -1);
    //for (int i = 0; i < n(); i++) if (m_matchIdx[i] < 0) m_queue.push(i);
    for (std::set<int>::iterator it = freeX.begin(); it != freeX.end(); it++)
      if (m_matchIdx[*it] < 0)
        m_queue.push(*it);
    m_Y = -1;
    while (!m_queue.empty()) {
      int u = m_queue.front();
      m_queue.pop();
      if (u < n()) {
        NeighborHood1 nb(*this, u, m_r, true);
        m_tree->applyJob(nb);
        if (m_Y >= 0) {
          m_count++;
          break;
        }
        if (!nb.isFound()) // remove u from candidate sets
          freeX.erase(u);
      } else {
        int v = m_matchIdx[u];
        if (m_prev[v] < 0) {
          m_prev[v] = u;
          m_queue.push(v);
        }
      }
    }

    Log::m_log << m_count << " ";
    Log::m_log.flush();
    int v = m_Y;
    while (v >= 0) {
      int u = m_prev[v];
      m_matchIdx[u] = v;
      m_matchIdx[v] = u;
      v = m_prev[u];
    }
  } while (m_Y >= 0);
  Log::m_log << endl;
}

StableMatching::StableMatching(const dataset_type & set1, const dataset_type &set2, double r) :
  MaximumMatching(set1, set2, r)
{
}

void StableMatching::doMatch()
{
  computeNeighbors();
}
